package DFS;

public class findCircleNum {
    private int n;

    public int findCircleNum(int[][] M) {
        int n = M.length;
        int circleNum = 0;
        boolean[] hasVisited = new boolean[n];
        for (int i = 0; i < n; i++) {
            if (!hasVisited[i]) {
                dfs(M, i, hasVisited);
                circleNum++;
            }
        }
        return circleNum;
    }

    private void dfs(int[][] M, int i, boolean[] hasVisited) {
        hasVisited[i] = true;
        for (int j = 0; j < n; j++) {
            if (!hasVisited[j] && M[i][j] == 1) {
                dfs(M, j , hasVisited);
            }
        }
    }
}
